home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / access / index-rtree / rtscan.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  9.1 KB  |  395 lines
  1. /*
  2.  *  rtscan.c -- routines to manage scans on index relations
  3.  */
  4. #include "tmp/c.h"
  5. #include "tmp/postgres.h"
  6.  
  7. #include "storage/bufmgr.h"
  8. #include "storage/bufpage.h"
  9. #include "storage/page.h"
  10.  
  11. #include "utils/log.h"
  12. #include "utils/rel.h"
  13.  
  14. #include "access/heapam.h"
  15. #include "access/genam.h"
  16. #include "access/ftup.h"
  17. #include "access/rtree.h"
  18.  
  19. /* routines defined and used here */
  20. extern void    rtregscan();
  21. extern void    rtdropscan();
  22. extern void    rtadjone();
  23. extern void    adjuststack();
  24. extern void    adjustiptr();
  25.  
  26. /*
  27.  *  Whenever we start an rtree scan in a backend, we register it in private
  28.  *  space.  Then if the rtree index gets updated, we check all registered
  29.  *  scans and adjust them if the tuple they point at got moved by the
  30.  *  update.  We only need to do this in private space, because when we update
  31.  *  an rtree we have a write lock on the tree, so no other process can have
  32.  *  any locks at all on it.  A single transaction can have write and read
  33.  *  locks on the same object, so that's why we need to handle this case.
  34.  */
  35.  
  36. typedef struct RTScanListData {
  37.     IndexScanDesc        rtsl_scan;
  38.     struct RTScanListData    *rtsl_next;
  39. } RTScanListData;
  40.  
  41. typedef RTScanListData    *RTScanList;
  42.  
  43. /* pointer to list of local scans on rtrees */
  44. static RTScanList RTScans = (RTScanList) NULL;
  45.  
  46. RcsId("$Header: /private/postgres/src/access/index-rtree/RCS/rtscan.c,v 1.3 1991/05/22 07:44:57 mao Exp $");
  47.  
  48. IndexScanDesc
  49. rtbeginscan(r, fromEnd, nkeys, key)
  50.     Relation r;
  51.     Boolean fromEnd;
  52.     uint16 nkeys;
  53.     ScanKey key;
  54. {
  55.     IndexScanDesc s;
  56.  
  57.     RelationSetLockForRead(r);
  58.     s = RelationGetIndexScan(r, fromEnd, nkeys, key);
  59.     rtregscan(s);
  60.  
  61.     return (s);
  62. }
  63.  
  64. void
  65. rtrescan(s, fromEnd, key)
  66.     IndexScanDesc s;
  67.     Boolean fromEnd;
  68.     ScanKey key;
  69. {
  70.     RTreeScanOpaque p;
  71.     int nbytes;
  72.  
  73.     if (!IndexScanIsValid(s)) {
  74.     elog(WARN, "rtrescan: invalid scan.");
  75.     return;
  76.     }
  77.  
  78.     /*
  79.      *  Clear all the pointers.
  80.      */
  81.  
  82.     ItemPointerSetInvalid(&s->previousItemData);
  83.     ItemPointerSetInvalid(&s->currentItemData);
  84.     ItemPointerSetInvalid(&s->nextItemData);
  85.     ItemPointerSetInvalid(&s->previousMarkData);
  86.     ItemPointerSetInvalid(&s->currentMarkData);
  87.     ItemPointerSetInvalid(&s->nextMarkData);
  88.  
  89.     /*
  90.      *  Set flags.
  91.      */
  92.     if (RelationGetNumberOfBlocks(s->relation) == 0) {
  93.     s->flags = ScanUnmarked;
  94.     } else if (fromEnd) {
  95.     s->flags = ScanUnmarked | ScanUncheckedPrevious;
  96.     } else {
  97.     s->flags = ScanUnmarked | ScanUncheckedNext;
  98.     }
  99.  
  100.     s->scanFromEnd = fromEnd;
  101.  
  102.     if (s->numberOfKeys > 0) {
  103.     bcopy( (Pointer)&key->data[0],            /* from */
  104.            (Pointer)&s->keyData.data[0],        /* to */
  105.            s->numberOfKeys * sizeof (key->data[0])    /* nbytes */
  106.     );
  107.     }
  108.  
  109.     p = (RTreeScanOpaque) s->opaque;
  110.     if (p != (RTreeScanOpaque) NULL) {
  111.     freestack(p->s_stack);
  112.     freestack(p->s_markstk);
  113.     p->s_stack = p->s_markstk = (RTSTACK *) NULL;
  114.     p->s_flags = 0x0;
  115.     } else {
  116.     int i;
  117.  
  118.     /* initialize opaque data */
  119.     nbytes = sizeof(RTreeScanOpaqueData);
  120.     if (s->numberOfKeys > 0) {
  121.         nbytes += (s->numberOfKeys - 1)
  122.               * sizeof(ScanKeyEntryData);
  123.     }
  124.  
  125.     s->opaque = (Pointer) palloc(nbytes);
  126.     p = (RTreeScanOpaque) s->opaque;
  127.     p->s_stack = p->s_markstk = (RTSTACK *) NULL;
  128.     p->s_internalNKey = s->numberOfKeys;
  129.     p->s_flags = 0x0;
  130.     if (s->numberOfKeys > 0) {
  131.         nbytes = s->numberOfKeys * sizeof(ScanKeyEntryData);
  132.         bcopy(&(s->keyData.data[0]), &(p->s_internalKey.data[0]), nbytes);
  133.  
  134.         for (i = 0; i < s->numberOfKeys; i++) {
  135.         p->s_internalKey.data[i].procedure =
  136.            RTMapOperator(s->relation,
  137.                  s->keyData.data[i].attributeNumber,
  138.                  s->keyData.data[i].procedure);
  139.         }
  140.     }
  141.     }
  142. }
  143.  
  144. void
  145. rtmarkpos(s)
  146.     IndexScanDesc s;
  147. {
  148.     RTreeScanOpaque p;
  149.     RTSTACK *o, *n, *tmp;
  150.  
  151.     s->currentMarkData = s->currentItemData;
  152.     p = (RTreeScanOpaque) s->opaque;
  153.     if (p->s_flags & RTS_CURBEFORE)
  154.     p->s_flags |= RTS_MRKBEFORE;
  155.     else
  156.     p->s_flags &= ~RTS_MRKBEFORE;
  157.  
  158.     o = (RTSTACK *) NULL;
  159.     n = p->s_stack;
  160.  
  161.     /* copy the parent stack from the current item data */
  162.     while (n != (RTSTACK *) NULL) {
  163.     tmp = (RTSTACK *) palloc(sizeof(RTSTACK));
  164.     tmp->rts_child = n->rts_child;
  165.     tmp->rts_blk = n->rts_blk;
  166.     tmp->rts_parent = o;
  167.     o = tmp;
  168.     n = n->rts_parent;
  169.     }
  170.  
  171.     freestack(p->s_markstk);
  172.     p->s_markstk = o;
  173. }
  174.  
  175. void
  176. rtrestrpos(s)
  177.     IndexScanDesc s;
  178. {
  179.     RTreeScanOpaque p;
  180.     RTSTACK *o, *n, *tmp;
  181.  
  182.     s->currentItemData = s->currentMarkData;
  183.     p = (RTreeScanOpaque) s->opaque;
  184.     if (p->s_flags & RTS_MRKBEFORE)
  185.     p->s_flags |= RTS_CURBEFORE;
  186.     else
  187.     p->s_flags &= ~RTS_CURBEFORE;
  188.  
  189.     o = (RTSTACK *) NULL;
  190.     n = p->s_markstk;
  191.  
  192.     /* copy the parent stack from the current item data */
  193.     while (n != (RTSTACK *) NULL) {
  194.     tmp = (RTSTACK *) palloc(sizeof(RTSTACK));
  195.     tmp->rts_child = n->rts_child;
  196.     tmp->rts_blk = n->rts_blk;
  197.     tmp->rts_parent = o;
  198.     o = tmp;
  199.     n = n->rts_parent;
  200.     }
  201.  
  202.     freestack(p->s_stack);
  203.     p->s_stack = o;
  204. }
  205.  
  206. void
  207. rtendscan(s)
  208.     IndexScanDesc s;
  209. {
  210.     RTreeScanOpaque p;
  211.  
  212.     p = (RTreeScanOpaque) s->opaque;
  213.  
  214.     if (p != (RTreeScanOpaque) NULL) {
  215.     freestack(p->s_stack);
  216.     freestack(p->s_markstk);
  217.     }
  218.  
  219.     rtdropscan(s);
  220.     /* XXX don't unset read lock -- two-phase locking */
  221. }
  222.  
  223. void
  224. rtregscan(s)
  225.     IndexScanDesc s;
  226. {
  227.     RTScanList l;
  228.  
  229.     l = (RTScanList) palloc(sizeof(RTScanListData));
  230.     l->rtsl_scan = s;
  231.     l->rtsl_next = RTScans;
  232.     RTScans = l;
  233. }
  234.  
  235. void
  236. rtdropscan(s)
  237.     IndexScanDesc s;
  238. {
  239.     RTScanList l;
  240.     RTScanList prev;
  241.  
  242.     prev = (RTScanList) NULL;
  243.  
  244.     for (l = RTScans;
  245.      l != (RTScanList) NULL && l->rtsl_scan != s;
  246.      l = l->rtsl_next) {
  247.     prev = l;
  248.     }
  249.  
  250.     if (l == (RTScanList) NULL)
  251.     elog(WARN, "rtree scan list corrupted -- cannot find 0x%lx", s);
  252.  
  253.     if (prev == (RTScanList) NULL)
  254.     RTScans = l->rtsl_next;
  255.     else
  256.     prev->rtsl_next = l->rtsl_next;
  257.  
  258.     pfree (l);
  259. }
  260.  
  261. void
  262. rtadjscans(r, op, blkno, offind)
  263.     Relation r;
  264.     int op;
  265.     BlockNumber blkno;
  266.     OffsetIndex offind;
  267. {
  268.     RTScanList l;
  269.     ObjectId relid;
  270.  
  271.     relid = r->rd_id;
  272.     for (l = RTScans; l != (RTScanList) NULL; l = l->rtsl_next) {
  273.     if (l->rtsl_scan->relation->rd_id == relid)
  274.         rtadjone(l->rtsl_scan, op, blkno, offind);
  275.     }
  276. }
  277.  
  278. /*
  279.  *  rtadjone() -- adjust one scan for update.
  280.  *
  281.  *    By here, the scan passed in is on a modified relation.  Op tells
  282.  *    us what the modification is, and blkno and offind tell us what
  283.  *    block and offset index were affected.  This routine checks the
  284.  *    current and marked positions, and the current and marked stacks,
  285.  *    to see if any stored location needs to be changed because of the
  286.  *    update.  If so, we make the change here.
  287.  */
  288.  
  289. void
  290. rtadjone(s, op, blkno, offind)
  291.     IndexScanDesc s;
  292.     int op;
  293.     BlockNumber blkno;
  294.     OffsetIndex offind;
  295. {
  296.     RTreeScanOpaque so;
  297.  
  298.     adjustiptr(s, &(s->currentItemData), op, blkno, offind);
  299.     adjustiptr(s, &(s->currentMarkData), op, blkno, offind);
  300.  
  301.     so = (RTreeScanOpaque) s->opaque;
  302.  
  303.     if (op == RTOP_SPLIT) {
  304.     adjuststack(so->s_stack, blkno, offind);
  305.     adjuststack(so->s_markstk, blkno, offind);
  306.     }
  307. }
  308.  
  309. /*
  310.  *  adjustiptr() -- adjust current and marked item pointers in the scan
  311.  *
  312.  *    Depending on the type of update and the place it happened, we
  313.  *    need to do nothing, to back up one record, or to start over on
  314.  *    the same page.
  315.  */
  316.  
  317. void
  318. adjustiptr(s, iptr, op, blkno, offind)
  319.     IndexScanDesc s;
  320.     ItemPointer iptr;
  321.     int op;
  322.     BlockNumber blkno;
  323.     OffsetIndex offind;
  324. {
  325.     OffsetIndex curoff;
  326.     RTreeScanOpaque so;
  327.  
  328.     if (ItemPointerIsValid(iptr)) {
  329.     if (ItemPointerGetBlockNumber(iptr) == blkno) {
  330.         curoff = ItemPointerGetOffsetNumber(iptr, 0);
  331.         so = (RTreeScanOpaque) s->opaque;
  332.  
  333.         switch (op) {
  334.           case RTOP_DEL:
  335.         /* back up one if we need to */
  336.         if (curoff > offind) {
  337.  
  338.             if (curoff > 1) {
  339.             /* just adjust the item pointer */
  340.             ItemPointerSet(iptr, 0, blkno, 0, curoff - 1);
  341.             } else {
  342.             /* remember that we're before the current tuple */
  343.             ItemPointerSet(iptr, 0, blkno, 0, 1);
  344.             if (iptr == &(s->currentItemData))
  345.                 so->s_flags |= RTS_CURBEFORE;
  346.             else
  347.                 so->s_flags |= RTS_MRKBEFORE;
  348.             }
  349.         }
  350.         break;
  351.  
  352.           case RTOP_SPLIT:
  353.         /* back to start of page on split */
  354.         ItemPointerSet(iptr, 0, blkno, 0, 1);
  355.         if (iptr == &(s->currentItemData))
  356.             so->s_flags &= ~RTS_CURBEFORE;
  357.         else
  358.             so->s_flags &= ~RTS_MRKBEFORE;
  359.         break;
  360.  
  361.           default:
  362.         elog(WARN, "Bad operation in rtree scan adjust: %d", op);
  363.         }
  364.     }
  365.     }
  366. }
  367.  
  368. /*
  369.  *  adjuststack() -- adjust the supplied stack for a split on a page in
  370.  *             the index we're scanning.
  371.  *
  372.  *    If a page on our parent stack has split, we need to back up to the
  373.  *    beginning of the page and rescan it.  The reason for this is that
  374.  *    the split algorithm for rtrees doesn't order tuples in any useful
  375.  *    way on a single page.  This means on that a split, we may wind up
  376.  *    looking at some heap tuples more than once.  This is handled in the
  377.  *    access method update code for heaps; if we've modified the tuple we
  378.  *    are looking at already in this transaction, we ignore the update
  379.  *    request.
  380.  */
  381.  
  382. void
  383. adjuststack(stk, op, blkno, offind)
  384.     RTSTACK *stk;
  385.     BlockNumber blkno;
  386.     OffsetIndex offind;
  387. {
  388.     while (stk != (RTSTACK *) NULL) {
  389.     if (stk->rts_blk == blkno)
  390.         stk->rts_child = 0;
  391.  
  392.     stk = stk->rts_parent;
  393.     }
  394. }
  395.